package my.suveng.leetcode.stack;

import my.suveng.util.json.Jackson;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树中序遍历
 * @author suwenguang
 **/
public class S94 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = null;
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        Solution solution = new Solution();
        List<Integer> integers = solution.inorderTraversal(root);
        System.out.println(Jackson.toJsonString(integers));

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        System.out.println(Jackson.toJsonString(solution.inorderTraversal(root)));

        root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        System.out.println(Jackson.toJsonString(solution.inorderTraversal(root)));

    }


//给定一个二叉树，返回它的中序 遍历。
//
// 示例:
//
// 输入: [1,null,2,3]
//   1
//    \
//     2
//    /
//   3
//
//输出: [1,3,2]
//
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
// Related Topics 栈 树 哈希表
// 👍 584 👎 0


//leetcode submit region begin(Prohibit modification and deletion)


    //leetcode submit region end(Prohibit modification and deletion)
    static class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            return s2(root);

        }

        /**
         * 使用栈迭代解答
         */
        private List<Integer> s1(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode curr = root;
            while (curr != null || !stack.isEmpty()) {
                while (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                }

                curr = stack.pop();
                res.add(curr.val);
                curr = curr.right;
            }

            return res;
        }

        /**
         * 使用递归解答
         */
        private List<Integer> s2(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            s2help(root, res);
            return res;
        }

        private void s2help(TreeNode curr, List<Integer> res) {
            if (curr == null) {
                return;
            }
            // 递归条件
            if (curr.left != null) {
                s2help(curr.left, res);
            }
            res.add(curr.val);
            s2help(curr.right, res);
        }


    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}



